package com.wen.Part6.GraphAlgorithm.impl;

import com.wen.Part6.DataStructure.Edge;
import com.wen.Part6.DataStructure.Graph;
import com.wen.Part6.GraphAlgorithm.GraphAlgorithm;
import com.wen.Part6.GraphAlgorithm.GraphUtils;

import java.util.Arrays;

public class Bellman_Ford implements GraphAlgorithm {
    private String start;

    public Bellman_Ford(String start) {
        this.start = start;
    }

    @Override
    public Object solve(Graph g) {
        int[] dist = new int[g.getSize()];
        int[] path = new int[g.getSize()];
        Arrays.fill(dist,999);
        dist[g.key2Index(start)] = 0;
        for (int i = 0; i < g.getSize(); i++) {
            path[i] = i;
        }

        boolean flag = true;
        for (int i = 0; i < g.getSize(); i++) {
            flag = true;
            for (Edge edge : g.getEdges()) {
                if (dist[edge.getStart()] + edge.getValue() < dist[edge.getEnd()]){
                    flag = false;
                     dist[edge.getEnd()] = dist[edge.getStart()] + edge.getValue();
                     path[edge.getEnd()] = edge.getStart();
                }
            }
            if (flag)break;
        }
        System.out.println(Arrays.toString(path));
        System.out.println(Arrays.toString(dist));
        GraphUtils.printPath(g,start,dist,path);
        return null;
    }
}
